import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class BinarySearchTree<E extends Comparable<E>> {
  private static class Node<E> {
    public E data;
    public Node<E> l;
    public Node<E> r;

    public Node(E data) {
      this.data = data;
      this.l = this.r = null;
    }
  }

  private Node<E> root;

  public BinarySearchTree() {
    root = null;
  }

  public void add(E e) {
    var newNode = new Node<>(e);
    if (root == null) {
      root = newNode;
    } else {
      // 在已有树中新增节点
      insert(root, e);
    }
  }

  /**
   * 在root中插入新增节点, 并返回root
   *
   * @param root - 根节点
   * @param e - 新增数据
   * @return - 返回插入数据后的根节点
   */
  private static <T extends Comparable<T>> Node<T> insert(Node<T> root, T e) {
    var newNode = new Node<>(e);
    if (root == null) {
      return newNode;
    }

    if (root.data.compareTo(e) > 0) {
      root.l = insert(root.l, e);
    } else if (root.data.compareTo(e) < 0) {
      root.r = insert(root.r, e);
    } else {
      // 已经有啦
      System.out.println("已有这个节点了:" + e);
    }
    return root;
  }

  private static <E> void travelTree(Node<E> root, Collection<E> collection) {
    if (root == null) return;
    travelTree(root.l, collection);
    collection.add(root.data);
    travelTree(root.r, collection);
  }

  public List<E> toList() {
    var list = new ArrayList<E>();
    travelTree(root, list);
    return list;
  }

  @Override
  public String toString() {
    var list = new ArrayList<E>();

    travelTree(root, list);
    return this.getClass().getName() + ": " + list.toString();
  }
}
